1. Field of the Invention
The present invention relates to compilers and numerical computations. More specifically, the present invention relates to a method and an apparatus for automatically producing efficient code for computing derivatives and/or slopes of functions within in a digital computer system.
2. Related Art
Computer systems are routinely used to solve non-linear problems, including, but not limited to: systems of non-linear equations, ordinary and partial differential equations, and global optimization problems. Global optimization problems, for example, occur in applications as diverse as predicting the weather, designing an aircraft engine or optimizing a financial portfolio. In order to solve non-linear problems, expressions for the first, second and even higher order derivatives of functions and constraint equations are typically needed.
These expressions for derivatives can be generated automatically through a technique known as “automatic differentiation” (AD), which symbolically differentiates binary operations within in a code list. For example, the expression,       f    ⁡          (      x      )        =            x      +      1              sin      ⁡              (                  x          +          1                )            can be represented in code list form as,
TABLE 1T1 = X + 1T2 = X + 1T3 = SIN(T2)F = T1/T3The corresponding derivative of this expression is,             ⅆ              f        ⁡                  (          x          )                            ⅆ              (        x        )              =                    sin        ⁡                  (                      x            +            1                    )                    -                        (                      x            +            1                    )                ⁢                  cos          ⁡                      (                          x              +              1                        )                                              sin        2            ⁡              (                  x          +          1                )            which can be represented in code list form including derivatives of temporary variables as,
TABLE 2T1 = X + 1D1 = 1T2 = SIN(T1)D2 = COS(T1)*D1T3 = X + 1D3 = 1T4 = COS(T3)D4 = SIN(T3)*D3T5 = X + 1D5 = 1T6 = T5*T4D6 = T5*D4 + T4*D5T7 = T2 − T6D7 = D2 − D6T8 = X + 1D8 = 1T9 = SIN(T8)D9 = COS(T8)*D8T10 = T9**2D10 = 2*T9*D9F = T7/T10DF = (T10*D7 − T7*D10)/T10**2
Note that automatic differentiation creates an unnecessary explosion in the number of temporary variables. This causes a number of negative consequences because (1) unnecessary temporary variables consume memory; (2) computing unnecessary temporary variables needlessly slows execution; and (3) in a interval arithmetic context, unnecessary temporary variables introduce unnecessary dependencies that produce unnecessarily wide interval results.
What is needed is a method and an apparatus for automatically generating code to calculate derivatives of an expression without generating unnecessary temporary variables.